package leetcode._20;

import java.util.Stack;

class Solution {

	public static void main(String[] args) {
		Solution s = new Solution();
		System.out.println(s.isValid("()")); // true
		System.out.println(s.isValid("()[]{}")); // true
		System.out.println(s.isValid("(]")); // false
		System.out.println(s.isValid("([)]")); // false
		System.out.println(s.isValid("{[]}")); // true
	}

	public boolean isValid(String s) {
		Stack<Character> stack = new Stack<>();
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if (c == '(' || c == '{' || c == '[') {
				stack.push(c);
			} else {
				if (stack.isEmpty())
					return false;
				Character tc = stack.pop();
				if (c == ')' && tc != '(')
					return false;
				if (c == '}' && tc != '{')
					return false;
				if (c == ']' && tc != '[')
					return false;
			}
		}
		return stack.isEmpty();
	}
}
